package com.lh.jianzhioffer.专项练习.数组;

/**
 * @author: linghao
 * @since: 2023/2/26
 *
 * 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 * 实现 NumMatrix 类：
 *
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和
 *
 * 一维前缀和
 */
public class 二维子矩阵的和013 {

    int[][] sums;

    public 二维子矩阵的和013(int[][] matrix) {
        int m = matrix.length;
        if(m>0){
            int n = matrix[0].length;
            sums = new int[m][n+1];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    sums[i][j+1] = sums[i][j]+matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i=row1;i<=row2;i++){
            sum += sums[i][col2+1] - sums[i][col1];
        }
        return sum;
    }
}
